package algorithm_optimal_solution.StackAndQueue;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

//生成窗口最大值数组：使用双端队列，设置成头大尾小，用于保存下标。尾部删除比新传入的数小的数，然后新数添加到尾部；删除已经过期的头部数；判断位数再保存结果
public class WindowMaxArray {

    //普通递归解法，花费O(n^2)
    public void iteratorCount()throws IOException{
        BufferedReader scanner = new BufferedReader(new InputStreamReader(System.in));
        int len = Integer.parseInt(scanner.readLine());
        String[] value = scanner.readLine().split(" ");
        int[] arr = new int[value.length];
        for(int i = 0;i<value.length;i++){
            arr[i] = Integer.parseInt(value[i]);
        }
        int[][] twoArr = new int[len][2];
        for(int i=0;i<len;i++){
            int num = arr[i];
            int leftLess = i;
            int rightLess = i;
            do{
                leftLess--;
            }while(leftLess>-1 && arr[leftLess] > arr[i]);
            do{
                rightLess--;
            }while(rightLess>-1 || arr[rightLess] > arr[i]);
            twoArr[i] = new int[]{leftLess,rightLess};
        }
        StringBuilder sb = new StringBuilder();
        for(int[] i:twoArr){
            sb.append(i[0]).append(" ").append(i[1]).append("\n");
        }
        System.out.print(sb);
    }

    //双端队列解法，花费O(n)
    public int[] getMaxWindowArray(int[] arr,int windowLen){
        if(arr == null || arr.length < windowLen){
            return null;
        }
        Deque<Integer> maxQueue = new LinkedList<>();
        int[] result = new int[arr.length - windowLen + 1];
        int len = arr.length;
        int index = 0;
        for(int i=0;i<len;i++){
            while(!maxQueue.isEmpty() && arr[maxQueue.peekLast()] <= arr[i]){
                maxQueue.pollLast();
            }
            maxQueue.offerLast(i);
            if(maxQueue.peekFirst() == i - windowLen){
                maxQueue.pollFirst();
            }
            if(i >= windowLen - 1){
                result[index++] = arr[maxQueue.peekFirst()];
            }
        }
        return result;
    }

    public static void main(String[] args)throws IOException{
        BufferedReader scanner = new BufferedReader(new InputStreamReader(System.in));
        String value = scanner.readLine();
        String[] splitValue = value.split(" ");
        int len = Integer.parseInt(splitValue[0]);
        int windowLen = Integer.parseInt(splitValue[1]);
        String[] numbers = scanner.readLine().split(" ");
        int[] arr = new int[len];
        for(int i=0;i<len;i++){
            int number = Integer.parseInt(numbers[i]);
            arr[i] = number;
        }
        int[] result = new WindowMaxArray().getMaxWindowArray(arr, windowLen);
        System.out.println(Arrays.toString(result));
    }
}
